package chapter2;

/**
 * @author Hang
 * @date 2022/8/11
 * @project AutumnOffer
 * @description 面试题14 题目1
 **/
public class cuttingRope {
    public static void main(String[] args) {
        int n = 10;
        System.out.println(cuttingRope(n));
    }
    public static int cuttingRope(int n) {
        int[] res = new int[n+1]; // 定义动态规划数组
        res[1] = 1;//初始值
        for(int i=2;i<=n;i++){ //从2开始
            int max = 0; // 比较每次的最大值
            for(int j=1;j<=i/2;j++){ //因为对称性，所以只需要一半即可
                int pro = Math.max((i-j)*j,res[i-j] * j);//用于比较减或者不减
                if(max <= pro) max = pro;
            }
            res[i] = max;//最大值
        }
        return res[n];
    }
}
